package cn.kent.middle;


/**
 * 162. 寻找峰值
 * 二分法
 */
public class FindPeakElement {
    public static void main(String[] args) {
//        int[] nums = {1,2,1,3,5,4};
//        int[] nums = {1,2,1};
//        int[] nums = {1};
        int[] nums = {1, 2, 3, 1};
        System.out.println(findPeakElement3(nums));
    }


    /****
     * 二分查找 优化迭代爬坡
     * 时间复杂度： O(logn)
     */
    public static int findPeakElement3(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (compare(nums, mid - 1, mid) < 0 && compare(nums, mid, mid + 1) > 0) {
                ans = mid;
                break;
            }
            if (compare(nums, mid, mid + 1) < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }

    /****
     * 迭代爬坡
     * O(n) 时间复杂度
     */
    public static int findPeakElement2(int[] nums) {
        int n = nums.length;
        int idx = (int) (Math.random() * n);

        while (!(compare(nums, idx - 1, idx) < 0 && compare(nums, idx, idx + 1) > 0)) {
            if (compare(nums, idx, idx + 1) < 0) {
                idx += 1;
            } else {
                idx -= 1;
            }
        }
        return idx;
    }

    // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
    // 方便处理 nums[-1] 以及 nums[n] 的边界情况
    public static int[] get(int[] nums, int idx) {
        if (idx == -1 || idx == nums.length) {
            return new int[]{0, 0};
        }
        return new int[]{1, nums[idx]};
    }

    public static int compare(int[] nums, int idx1, int idx2) {
        int[] num1 = get(nums, idx1);
        int[] num2 = get(nums, idx2);
        if (num1[0] != num2[0]) {
            return num1[0] > num2[0] ? 1 : -1;
        }
        if (num1[1] == num2[1]) {
            return 0;
        }
        return num1[1] > num2[1] ? 1 : -1;
    }


    /**********
     * 二分法失败运行
     */
    public static int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        return recursion(nums, l, r);
    }


    private static int recursion(int[] nums, int l, int r) {
        if (l <= r) {
            int mid = (l + r) / 2;
            if (mid + 1 <= r && mid - 1 >= l && nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                return mid;
            } else if (mid - 1 >= l && nums[mid] < nums[mid - 1]) {
                r = mid - 1;
                return recursion(nums, l, r);
            } else if (mid + 1 <= r && nums[mid] < nums[mid + 1]) {
                l = mid + 1;
                return recursion(nums, l, r);
            }
        }
        return -1;
    }
}
